/**

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

*/


class Solution {
    List<List<Integer>>  res=new ArrayList();
    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k,1,n,0,new ArrayList());
        return res;
    }
    public void dfs(int n,int start, int target,int sum,List<Integer> path ){
        if(sum>target){
            return;
        }
        if(n==path.size()){
            if(sum==target){
               res.add(new ArrayList(path)); 
            }
            return;
        }
        for(int i=start;i<=9;i++){
            path.add(i);
            sum=sum+i;
            dfs(n,i+1,target,sum,path);
            path.remove(path.size()-1);
            sum=sum-i;
        }
    }
}